package 栈和队列;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.regex.Pattern;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-02
 */
public class 实现逆波兰式 {
    public static void main(String[] args) {
        System.out.println(8 - 1 - 6 * (5 - 2) - 8 * 9 - 2);
        valid("88*(8-1*5)");
        postFix("88*88*(8--1*5)".trim());
    }

    public static boolean valid(String str) {
        Stack<String> oper = new Stack<>();
        for (int i = 0; i < str.length() - 1; i++) {
            String current = str.charAt(i) + "";
            while (isNumber(str.charAt(i + 1) + "")) {
                current += str.charAt(i + 1);
                i++;
            }
            String next = str.charAt(i + 1) + "";
            while (isNumber(str.charAt(i + 1) + "")) {
                next += str.charAt(i + 1);
                i++;
            }
            if (isOper(current) && isOper(next)) {
                return false;
            }
            if (current.equals("(")) {
                oper.push("(");
            }
            if (current.equals(")")) {
                if (!oper.isEmpty() && oper.peek().equals("(")) {
                    oper.pop();
                } else {
                    return false;
                }
            }
        }
        if (oper.size() != 0) {
            return false;
        }
        return true;
    }

    /**
     * 8-1-6*(5-2)-8*9-2     * 5-6*1     *     * @param source
     */
    public static void postFix(String source) {
        Queue query = new PriorityQueue((Comparator) (o1, o2) -> 0);
        if (!valid(source)) {
            System.out.println("输入有误");
            return;
        }
        Stack stackNum = new Stack<>();
        Stack<String> stackOp = new Stack<>();
        String num = "";
        for (int i = 0; i < source.length(); i++) {
            String temp = source.charAt(i) + "";
            if (!"".equals(num)) {
                //如果是数字
                stackNum.push(num);
                num = "";
            }
            switch (temp) {
                case "/":
                case "*":
                case "+":
                case "-":
                case "(":
                    if (temp.equals("(")) {
                        stackOp.push(temp);
                    } else if (stackOp.isEmpty() || compare(temp, stackOp.peek())) {
                        stackOp.push(temp);
                    } else {
                        while (!stackOp.isEmpty() && isOper(stackOp.peek()) && !compare(temp, stackOp.peek())) {
                            stackNum.push(stackOp.pop());
                        }
                        stackOp.push(temp);
                    }
                    break;
                case ")":
                    while (!stackOp.isEmpty() && !stackOp.peek().equals("(")) {
                        stackNum.push(stackOp.pop());
                    }
                    stackOp.pop();
                    break;
                default:
                    num += temp;
                    break;
            }
        }
        if (!"".equals(num)) {
            stackNum.push(num);
        }
        while (!stackOp.isEmpty()) {
            stackNum.push(stackOp.pop());
        }
        printStack(stackNum);
        calculate(stackNum);
    }

    public static void printStack(Stack stack) {
        System.out.println();
        stack.forEach(e -> System.out.print(e + "\t"));
    }

    public static boolean isOper(String a) {
        String s = "/*+-";
        return s.contains(a);
    }

    public static boolean isNumber(String source) {
        //        String containNum = ".*\\d.*";
        String num = "\\d+";
        if (source.startsWith("-")) {
            if (source.lastIndexOf("-") != 0) {
                return false;
            }
            source = source.substring(1);
        }
        if (source.contains(".")) {
            String[] splitArr = source.split("\\.");
            return splitArr.length == 2 && isNumber(splitArr[0]) && isNumber(splitArr[1]);
        }
        return Pattern.matches(num, source);
    }

    public static void calculate(Stack stack) {
        Stack<String> tempStack = new Stack<>();
        Stack<Integer> stackOp = new Stack<>();
        reverseStack(stack, tempStack);
        while (tempStack.size() != 0) {
            String temp = tempStack.peek();
            if (!isNumber(temp)) {
                tempStack.pop();
                Integer pre = stackOp.pop();
                Integer back = stackOp.pop();
                switch (temp) {
                    case "/":
                        tempStack.push((back / pre) + "");
                        break;
                    case "*":
                        tempStack.push((back * pre) + "");
                        break;
                    case "+":
                        tempStack.push((back + pre) + "");
                        break;
                    case "-":
                        tempStack.push((back - pre) + "");
                        break;
                }
            } else {
                stackOp.push(Integer.parseInt(tempStack.pop()));
            }
        }
        System.out.println(stackOp.peek());
    }

    public static void reverseStack(Stack source, Stack des) {
        while (!source.isEmpty()) {
            des.push(source.pop());
        }
    }

    public static boolean compare(String a, String b) {
        String[] arr1 = {"/*", "+-"};
        int aIndex = 0;
        int bIndex = 0;
        if (a.equals(b)) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i].contains(a)) {
                aIndex = i;
            }
            if (arr1[i].contains(b)) {
                bIndex = i;
            }
        }
        return aIndex < bIndex ? true : false;
    }
}